#include <cstdlib>
#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>
#include <ctime>

//最容易理解的算法，O(n^3)
long maxSumSub1(const std::vector<long> &A) {
    long maxSum = 0;
    for (long i = 0; i < (long)A.size(); ++i) {
        for (long j = i; j < (long)A.size(); ++j) {
            long thisSum = 0;
            for (long k = i; k <= j; ++k) {
                thisSum += A[k];
            }
            if (thisSum > maxSum) {
                maxSum = thisSum;
            }
        }
    }

    return maxSum;
}

//蛮力算法的改进版本，O(n^2)
long maxSumSub2(const std::vector<long> &A) {
    long maxSum = 0;
    for (long i = 0; i < (long)A.size(); ++i) {
        long thisSum = 0;
        for (long j = i; j < (long)A.size(); ++j) {
            thisSum += A[j];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            }
        }
    }
    return maxSum;
}

//递归算法，利用分而治之的思想，O(nlgn)
long maxSumSub3(const std::vector<long> &A, long l, long r) {
    if (l == r) {
        return A[l];
    }
    
    long m = (l+r)/2;
    long left = maxSumSub3(A, l, m);
    long right = maxSumSub3(A, m+1, r);

    long thisLeftSum = 0, leftMax = 0;
    for (long i = m; i >= l; --i) {
        thisLeftSum += A[i];
        if (thisLeftSum > leftMax) {
            leftMax = thisLeftSum;
        }
    }

    long thisRightSum = 0, rightMax = 0;
    for (long j = m+1; j <= r; ++j) {
        thisRightSum += A[j];
        if (thisRightSum > rightMax) {
            rightMax = thisRightSum;
        }
    }

    long tmpMax = std::max(left, right);
    return std::max(tmpMax, leftMax+rightMax);
}

//扫描算法，效率最高，最难理解，O(n)
long maxSumSub4(std::vector<long> Arr) {
    long maxSum = 0, thisSum = 0;

    for (long i = 0; i < (long)Arr.size(); ++i) {
        thisSum += Arr[i];
        if (thisSum > maxSum) {
            maxSum = thisSum;
        } else if (thisSum < 0) {
            thisSum = 0;
        }
    }

    return maxSum;
}


int main(void) {
    long A[] = {-4, -5, 3, 5, 7, -2, -3, 6, 9, 19, 22, -51, -6, -3};
    std::vector<long> Arr(A, A + sizeof(A)/sizeof(long));

    std::cout << "the squenue is : "; 
    std::copy(Arr.begin(), Arr.end(), std::ostream_iterator<long>(std::cout, " "));
    std::cout << std::endl;

    clock_t startCTime, endCTime;
    startCTime = clock();
    std::cout << "the maxSumSub1 and O(n^3) : " << maxSumSub1(Arr) << std::endl;
    std::cout << "the time is " << (double)(endCTime - startCTime)/CLOCKS_PER_SEC << "." << std::endl;
    endCTime = clock();
    
    
    startCTime = clock();
    std::cout << "the maxSumSub2 and O(n^2) : " << maxSumSub2(Arr) << std::endl;
    std::cout << "the time is " << (double)(endCTime - startCTime)/CLOCKS_PER_SEC << "." << std::endl;
    endCTime = clock();
    
    startCTime = clock();
    std::cout << "the maxSumSub3 and O(nlgn) : " << maxSumSub3(Arr, 0, Arr.size()-1) << std::endl;
    std::cout << "the time is " << (double)(endCTime - startCTime)/CLOCKS_PER_SEC << "." << std::endl;
    endCTime = clock();
    
    startCTime = clock();
    std::cout << "the maxSumSub4 and O(n) : " << maxSumSub4(Arr) << std::endl;
    std::cout << "the time is " << (double)(endCTime - startCTime)/CLOCKS_PER_SEC << "." << std::endl;
    endCTime = clock();

    system("pause");
    return 0;
}
